#include <functional>
#include <algorithm>
#include "cmf.h"
#include "exacto.h"

CliqueMaximaFronteraExacto::CliqueMaximaFronteraExacto(const Grafo& g) : CliqueMaximaFrontera(g) {
	
}

set<uint> CliqueMaximaFronteraExacto::resolver() {		
	set<uint> cliques;
	set<uint> solucion;
	uint cantRes = 0;
	uint gradosR = 0;
	
	backtracking(cliques, gradosR, grafo.conjuntoNodos(), solucion, cantRes);

	return solucion;
}

void CliqueMaximaFronteraExacto::backtracking(set<uint> &R, uint &gradosActuales, set<uint> P, set<uint> &res, uint &cantRes) {
	if(P.empty())
		return;

	set<uint> interseccion;
	int fronteraNueva;
	
	for(set<uint>::iterator it = P.begin(); it != P.end(); it++) {
		R.insert(*it);		
		gradosActuales += grafo.miGrado(*it);
		fronteraNueva = gradosActuales - R.size() * (R.size()-1);
		
		if(cantRes < fronteraNueva) {
			cantRes = fronteraNueva;
			res = R;			
		}
		
		interseccion = grafo.adyacentes(*it, P);
		backtracking(R, gradosActuales, interseccion, res, cantRes);

		R.erase(*it);
		gradosActuales -= grafo.miGrado(*it);
	}
}
